package com.atguigu.algorithm;

public class RobotWalk {
    public static void main(String[] args) {
        System.out.println(find(5, 2, 4, 5));
    }
    public static int find(int N,int S,int E,int k){
        return process(N,S,k,E);
    }
    //N为台阶阶数，cur为当前位置，res为剩余步数，E为目标位置
    public static int process(int N,int cur,int res,int E){
        if(res==0){ //剩余步数为0
            return cur==E?1:0;
        }
        if(cur==1){ //到达最左侧台阶，只能往右边走
            return process(N,2,res-1,E);
        }
        if(cur==N){ //到达最右侧台阶，只能往左走
            return process(N,N-1,res-1,E);
        }
        //中间位置
        return process(N,cur+1,res-1,E)+process(N,cur-1,res-1,E);
    }
}
